package com.chj.gaoji.class14;

import java.util.ArrayList;
import java.util.List;

public class Code09_PalindromePairs {
	public static List<List<Integer>> palindromePairs(String[] words) {
		Trie trie = new Trie();
		for (int i = 0; i < words.length; i++) {
			trie.insert(reverse(words[i]), i);
		}
		List<List<Integer>> res = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			res.addAll(findAll(trie, words[i], i));
		}
		return res;
	}

	public static List<List<Integer>> findAll(Trie trie, String word, int index) {
		List<List<Integer>> res = new ArrayList<>();
		int wLen = word.length();

		int rest = findWord(trie, "");
		if (rest != -1 && rest != index && word.equals(reverse(word))) {
			addRecord(res, rest, index);
			addRecord(res, index, rest);
		}

		int[] rs = manacherss(word);
		int mid = rs.length >> 1;
		for (int i = 1; i < mid; i++) {
			if (i - rs[i] == -1) {
				rest = findWord(trie, word.substring(wLen - (mid - i), wLen));
				if (rest != -1 && rest != index) {
					addRecord(res, rest, index);
				}
			}
		}
		for (int i = mid + 1; i < rs.length; i++) {
			if (i + rs[i] == rs.length) {
				rest = findWord(trie, word.substring(0, wLen - ((mid << 1) - i)));
				if (rest != -1 && rest != index) {
					addRecord(res, index, rest);
				}
			}
		}
		return res;
	}

	public static void addRecord(List<List<Integer>> res, int left, int right) {
		List<Integer> newr = new ArrayList<>();
		newr.add(left);
		newr.add(right);
		res.add(newr);
	}

	private static int findWord(Trie trie, String word) {
		Trie cur = trie;
		char[] chars = word.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int temp = chars[i] - 'a';
			if (cur.next[temp] == null)
				return -1;
			else
				cur = cur.next[temp];
		}
		return cur.end;
	}

	public static class Trie {
		Trie[] next;
		// end表示这目前这棵树是那一个索引单词的结尾
		int end;

		public Trie() {
			this.next = new Trie[26];
			this.end = -1;
		}

		// 由于待会儿用到字典树的时候，是找目标串的翻转字符串，所以插入的时候，应该是倒序插入
		public void insert(String s, int endNum) {
			char[] chars = s.toCharArray();
			Trie cur = this;
			for (int i = 0; i < chars.length; i++) {
				int index = chars[i] - 'a';
				if (cur.next[index] == null)
					cur.next[index] = new Trie();
				cur = cur.next[index];
			}
			cur.end = endNum;
		}
	}

//	public static int[] manacherss(String word) {
//		char[] mchs = manachercs(word);
//		int[] rs = new int[mchs.length];
//		int center = -1;
//		int pr = -1;
//		for (int i = 0; i != mchs.length; i++) {
//			rs[i] = pr > i ? Math.min(rs[(center << 1) - i], pr - i) : 1;
//			while (i + rs[i] < mchs.length && i - rs[i] > -1) {
//				if (mchs[i + rs[i]] != mchs[i - rs[i]]) {
//					break;
//				}
//				rs[i]++;
//			}
//			if (i + rs[i] > pr) {
//				pr = i + rs[i];
//				center = i;
//			}
//		}
//		return rs;
//	}

	public static int[] manacherss(String s) {
		if (s == null || s.length() == 0) {
			return new int[] {};
		}
		char[] str = manachercs(s); // 1221 -> #1#2#2#1#
		int[] pArr = new int[str.length]; // 回文半径数组
		int C = -1; // 中心
		int R = -1; // 回文右边界的再往右一个位置 最右的有效区是R-1位置
		for (int i = 0; i != str.length; i++) { // 每一个位置都求回文半径

			if (R < i) {
				pArr[i] = 1;
				while (i + pArr[i] < str.length && i - pArr[i] > -1) {
					if (str[i + pArr[i]] == str[i - pArr[i]])
						pArr[i]++;
					else {
						break;
					}
				}

				if (i + pArr[i] > R) {
					R = i + pArr[i] - 1;
					C = i;
				}
			}

			if (R >= i) {
				if (R - i < pArr[2 * C - i]) {
					pArr[i] = R - i;
					while (i + pArr[i] < str.length && i - pArr[i] > -1) {
						if (str[i + pArr[i]] == str[i - pArr[i]])
							pArr[i]++;
						else {
							break;
						}
					}

					if (i + pArr[i] > R) {
						R = i + pArr[i] - 1;
						C = i;
					}

				} else if (R - i == pArr[2 * C - i]) {
					pArr[i] = R - i;
				} else {
					pArr[i] = pArr[2 * C - i];
				}
			}
		}
		return pArr;
	}

	public static char[] manachercs(String word) {
		char[] chs = word.toCharArray();
		char[] mchs = new char[chs.length * 2 + 1];
		int index = 0;
		for (int i = 0; i != mchs.length; i++) {
			mchs[i] = (i & 1) == 0 ? '#' : chs[index++];
		}
		return mchs;
	}

	public static String reverse(String str) {
		char[] chs = str.toCharArray();
		int l = 0;
		int r = chs.length - 1;
		while (l < r) {
			char tmp = chs[l];
			chs[l++] = chs[r];
			chs[r--] = tmp;
		}
		return String.valueOf(chs);
	}

	public static List<List<Integer>> palindromePairs02(String[] words) {
		List<List<Integer>> ans = new ArrayList<>();
		int n = words.length;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)
					continue;
				if (!check(words[i] + words[j]))
					continue;
				List<Integer> temp = new ArrayList<>();
				temp.add(i);
				temp.add(j);
				ans.add(temp);
			}
		}
		return ans;
	}

	private static boolean check(String s) {
		int i = 0, j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) != s.charAt(j))
				return false;
			i++;
			j--;
		}
		return true;
	}

//	作者：copyreadmachine
//	链接：https://leetcode-cn.com/problems/palindrome-pairs/solution/java-trie-yi-yu-li-jie-by-copyreadmachine/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
//		{
//			String test = "112321";
//			System.out.println(String.valueOf(manachercs(test)));
//			int[] arr = manacherss(test);
//			for (int i = 0; i < arr.length; i++) {
//				System.out.print(arr[i] + " ");
//			}
//			System.out.println();
//		}

		{
//			输入：["abcd","dcba","lls","s","sssll"]
//		         输出：[[0,1],[1,0],[3,2],[2,4]] 
//			解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
//
//			来源：力扣（LeetCode）
//			链接：https://leetcode-cn.com/problems/palindrome-pairs
//			著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//			String[] words = new String[] { "", "abcd", "dcba", "lls", "s", "sssll", "" };
//			List<List<Integer>> res = palindromePairs(words);
//			System.out.println(res);
//			System.out.println("dcba".substring(0));
//			System.out.println("dcba".substring(1));
		}

		{
//			输入：["abcd","dcba","lls","s","sssll"]
//		         输出：[[0,1],[1,0],[3,2],[2,4]] 
//			解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
//
//			来源：力扣（LeetCode）
//			链接：https://leetcode-cn.com/problems/palindrome-pairs
//			著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
			String[] words = new String[] { "a", "abc", "aba", "" };
			List<List<Integer>> res = palindromePairs(words);
			System.out.println(res);
//			[[0,3],[3,0],[2,3],[3,2]]
		}

	}
}
